package tree;

/**
 * 889. 根据前序和后序遍历构造二叉树
 *
 * 给定两个整数数组，preorder和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，
 * postorder 是同一棵树的后序遍历，重构并返回二叉树。
 * 如果存在多个答案，您可以返回其中 任何 一个。
 */
public class ConstructTree_889 {
    // 自顶向下递归
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }

    // 前序遍历：根左右，后序遍历：左右根
    public TreeNode build(int[] preorder, int[] postorder, int preorderLeft, int preorderRight, int postorderLeft, int postorderRight) {
        if (preorderLeft > preorderRight || postorderLeft > postorderRight) {
            return null;
        }

        // 前序遍历的第一个元素即为根节点
        int rootVal = preorder[preorderLeft];
        TreeNode root = new TreeNode(rootVal);

        // 如果只有一个节点，直接返回即可，也可以避免下面的preorder[preorderLeft + 1]数组越界
        if (preorderLeft == preorderRight) {
            return root;
        }

        // 在后序遍历的数组中找出左子树的索引，其左边是左子树，右边是右子树
        int leftChildIndex = -1;
        for (int i = postorderLeft; i <= postorderRight; i++) {
            if (postorder[i] == preorder[preorderLeft + 1]) {
                leftChildIndex = i;
            }
        }

        // 左子树的节点个数
        int cnt = leftChildIndex - postorderLeft + 1;

        root.left = build(preorder, postorder, preorderLeft + 1, preorderLeft + cnt, postorderLeft, postorderLeft + cnt - 1);
        root.right = build(preorder, postorder, preorderLeft + cnt + 1, preorderRight, postorderLeft + cnt, postorderRight - 1);
        return root;
    }
}
